package DataStructure.array;

/**
 * 88. 合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array
 * 题目简述：将一个有效长度为m（实际容量m+n）的非递减数组nums1和一个有效长度为n的数组nums2并为一个非递减数组，结果存储在nums1中
 */
public class Merge {

    /**
     * 思路：双指针，p1指向num1的有效末尾，p2指向nums2的有效末尾，逐次比较选取较大的数字从实际末尾从后往前填充nums1
     * 最后若p1扫描完了p2还未扫描完，则直接将nums2剩余元素依次填充到nums1剩余位置
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m+n-1, p1=m-1, p2=n-1;
        while(p1 >=0 && p2 >= 0) {
            if(nums1[p1] > nums2[p2]) {
                nums1[i--] = nums1[p1--];
            } else {
                nums1[i--] = nums2[p2--];
            }
        }
        while(p2 >= 0) {
            nums1[i--] = nums2[p2--];
        }
    }
}
